# !/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
===========================
@Time : 2022/11/11 0011 21:08
@Author : 测试开发工程师
@File : 2. 列表查找 - 二分树.py
@Software: PyCharm
============================
"""

"""
什么是列表查找：
    在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。
    列表查找（线性表查找）：从列表中查找指定元素
    输入： 列表，待查找元素
    输出：元素下标（未找到元素时一般返回 None 或 -1）
    内置列表查找函数： index()

顺序查找：
    也叫线性查找，从列表第一个元素开始，顺序进行搜索，直到找到元素或 搜索到列表最后一个元素为止。

二分查找:  ========================= 必须是有序列表 =======================
    又叫折半查找，从有序列表的初始候选区 li[0:n] 开始，通过对待查找的值 与 候选区中间值的比较，可以使候选区减少一半

"""

from 算法.cal_time import cal_time


# 添加装饰器
@cal_time
def linear_search(li, val):  # 顺序查找 , 时间复杂度为 O(n)
    for ind, v in enumerate(li):
        if v == val:
            return ind
    else:
        return None


# 添加装饰器
@cal_time
def binary_search(li, val):  # 二分查找，时间复杂度 O(logn)
    left = 0
    right = len(li) - 1
    while left <= right:  # 候选区有值
        mid = (left + right) // 2  # 整除
        if li[mid] == val:
            return mid
        elif li[mid] > val:  # 待查找的值在 mid 左侧
            right = mid - 1
        else:  # li[mid] < val，待查找的值在 mid 右侧
            left = mid + 1
    else:  # 不满足 left <= right 则跳出循环
        return None


# li = [1, 2, 3, 4, 5, 6, 7, 8, 9]
# print(binary_search(li, 3))


li = list(range(10000))
# 顺序查找
print(linear_search(li, 3890))
# 二分树查找
print(binary_search(li, 3890))
